// 2025/3/30
// https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked
// 跳跃游戏2

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, n);
        dp[n - 1] = 0;
        for(int cur = n - 2; cur >= 0; cur--)
        {
            int end = cur + nums[cur];
            for(int i = cur + 1; i < n && i <= end; i++)
            {
                dp[cur] = min(dp[cur], dp[i]);
            }
            dp[cur]++;
        }
        return dp[0];
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, end = 0, step = 0, n = nums.size();
        for(int i = 0; i < n - 1; i++)
        {
            if(maxPos >= i)
            {
                maxPos = max(maxPos, i + nums[i]);
                if(i == end)
                {
                    end = maxPos;
                    ++step;
                }
            }
        }
        return step;
    }
};